#pragma once
#include <Image/Image.hpp>
#include <Algorithm/FibonacciHeap.hpp>

//find a path between two points in a image
//the path will track along the edges in the image
//before track, call Prepare() to prepare
//use SetStart() to set the startpoint
//Repetitively call FindPath() to track, used DP so will not be slow even if the image is large

namespace zzz{
class EdgeTracer
{
public:
  EdgeTracer(void);
  ~EdgeTracer(void);

  //mask, 1 to indicate edge region
  void SetMask(const Image<zuchar>& mask);
  void ClearMask();
  
  //call before process new image
  void Prepare(const Imagef &ori);
  void Prepare(const Image3f &ori);
  void Prepare(const Image4f &ori);
  
  //return idx of the nearest lowest link position
  //search range is defined by optrange_
  int OptimizeClick(int pos);
  Vector2ui OptimizeClick(const Vector2ui &pos);

  //set new start point
  void SetStart(int start);
  void SetStart(const Vector2ui &start);
  //after setting start, call FindPath real-time, data will be saved so wont be slow
  //data wont delete before next SetStart
  void FindPath(int end, vector<int>& backpath);
  void FindPath(const Vector2ui &end, vector<Vector2ui>& backpath);

  int optrange_;
private:
  void afterPrepare();
  //calculate links
  zzz::Array<2,Vector<8,float> > links_;
  float maxlink_;

  //start point
  int start_;

  //Fibonacci Heap for Dijkstra's algorithm
  struct Fibdata
  {
    float cost;
    int pos;
    bool operator<(const Fibdata& other)const {return cost<other.cost;}
  };
  FibonacciHeap<Fibdata> heap;

  //data for each pixel
  struct PathNode
  {
    FibonacciHeap<Fibdata>::NodeType* node;
    float cost;
    int backpath;
    int status;  //0: unchecked, 1: checking, 2: checked
  };
  Array<2,PathNode> pathmap;

  //mask
  Image<zuchar> mask_;
};
}
